#pragma once
#include<string>
#include<bitset>

//三个不同的Hash函数
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};
struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};
struct DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};


template<size_t N, // 要存的数据的个数
	size_t factor = 8, // 控制开空间大小的比例因子
	class K = string, // 键的类型
	class HashFunc1 = BKDRHash, 
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
class BloomFilter
{
public:
	void set(const K& key)
	{
		int len = N * facter;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;

		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}	
	void test(const K& key)
	{
		int len = N * facter;
		size_t index1 = HashFunc1()(key) % len;
		if (_bs.test(index1) == false)
			return false; // 准确的

		size_t index2 = HashFunc2()(key) % len;
		if (_bs.test(index2) == false)
			return false; // 准确的

		size_t index3 = HashFunc3()(key) % len;
		if (_bs.test(index3) == false)
			return false; // 准确的

		return true; // 可能三个位置都与其他数据冲突，所以存在误判
	}
private:
	bitset<N* facter> _bs;
};
